package cn.mayday.algorithms.year2021.month1.C双指针专题;

import java.util.Stack;

/**
 * 052
 *
 * @author Mayday05
 * @date 2021/5/12 10:16
 */
public class Offer052GetIntersectionNode {


    //Definition for singly-linked list.
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static void main(String[] args) {

    }


    /**
     * 巧妙方法：双指针【你走过我走过的路】
     * 时间复杂度
     *
     * @param headA 节点A
     * @param headB 节点B
     * @return 公共节点
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {

        // 分别指定临时节点A和临时节点B, 不改变原来链表结构
        ListNode tempA = headA;
        ListNode tempB = headB;

        // 利用指针A和指针B，分别走两个链表时，相同步数时一定相遇【你走过我的路】的特性
        while (tempA != tempB) {
            if (tempA != null) {
                tempA = tempA.next;
            } else {
                tempA = headB;
            }

            if (tempB != null) {
                tempB = tempB.next;
            } else {
                tempB = headA;
            }
        }
        return tempA;
    }

    // 思路：分别循环两个节点，比较节点数值是否相等，如果相等就返回

    // 方法二：辅助栈(通过)
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        Stack<ListNode> stackA = new Stack<>();
        Stack<ListNode> stackB = new Stack<>();
        // 分别指定临时节点A和临时节点B, 不改变原来链表结构
        ListNode tempA = headA;
        ListNode tempB = headB;

        // 链表A和链表B分别入栈
        while (tempA != null) {
            stackA.push(tempA);
            tempA = tempA.next;
        }
        while (tempB != null) {
            stackB.push(tempB);
            tempB = tempB.next;
        }

        // 如果出栈节点相等，就循环，直到第一个不相等
        ListNode result = null;
        while (!stackA.isEmpty() && !stackB.isEmpty()
                && stackA.peek() == stackB.peek()) {
            result = stackA.peek();
            stackA.pop();
            stackB.pop();
        }
        return result;
    }
}
